package org.example.Soution003;

import java.util.Deque;
import java.util.LinkedList;

public class StackDailyTemperature {
    public static void main(String[] args) {
        StackDailyTemperature s=new StackDailyTemperature();
        int[] temperatures=new int[]{73,74,75,71,69,72,76,73};
        int[] res=s.dailyTemperatures2(temperatures);
        for(int i=0;i<res.length;i++){
            System.out.print(res[i]+" ");
        }
    }

    //法二
    public int[] dailyTemperatures(int[] temperatures) {
        int n=temperatures.length;
        int[] res=new int[n];
        //辅助栈，记录阶段最大
        Deque<Integer> stack=new LinkedList<>();
        res[n-1]=0; stack.push(n-1);
        for(int i=n-2;i>=0;i--){
            int tempAdd=0;
            while(!stack.isEmpty()){
                if(temperatures[i]<temperatures[stack.peek()]){
                    res[i]=tempAdd+1;
                    stack.push(i);
                    break;
                }else if(temperatures[i]==temperatures[stack.peek()]){
                    if(res[stack.peek()]==0){
                        res[i]=0;
                    }else{
                        res[i]=tempAdd+1+res[stack.peek()];
                    }
                    stack.pop();
                    stack.push(i);
                    break;
                }else{
                    tempAdd+=res[stack.pop()];
                }
            }
            //这个数牛到把辅助栈清空了！
            if(stack.isEmpty()){
                res[i]=0;
                stack.push(i);
            }
        }
        return res;
    }

    public int[] dailyTemperatures2(int[] temperatures) {
        int n=temperatures.length;
        int[] res=new int[n];
        Deque<Integer> stack=new LinkedList<>();
        for(int i=0;i<n;i++){
            while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){
                int preIndex=stack.pop();
                res[preIndex]=i-preIndex;
            }
            stack.push(i);
        }
        return res;
    }
}
